#include <iostream>
#include <vector>
using namespace std;

class permutation {    
public:
    void backtrack(vector<vector<int> >& res, vector<int>& output, int first, int length) {
        if (first == length) {
            // length长度的排列结束
            res.__emplace_back(output);
            return;
        }

        for (int i = first; i < length; i++) {
            // 排好第i个位置
            swap(output[i], output[first]);
            // 操作下一个位置
            backtrack(res, output, first + 1, length);
            // 换回第i个位置
            swap(output[i], output[first]);
        }
    }

    vector<vector<int> > permute(vector<int>& nums) {
        vector<vector<int> > res;
        // 0到nums.size()进行排列
        backtrack(res, nums, 0, nums.size());
        return res;
    }
};

class permutationWithoutSame {
    vector<bool> vis;
    // 访问标记数组
public:
    void backtrack(vector<vector<int> >& res, vector<int>& nums, vector<int>& perm, int index) {
        if (index == nums.size()) {
            res.__emplace_back(perm);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]))
                continue;
            perm.__emplace_back(nums[i]);
            vis[i] = true;
            backtrack(res, nums, perm, index + 1);
            vis[i] = false;
            perm.pop_back();
        }
    }

    vector<vector<int> > permuteUnique(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> perm;
        vis.resize(nums.size());
        // 排序使相同数相邻
        sort(nums.begin(), nums.end());
        backtrack(res, nums, perm, 0);
        return res;
    }
};